﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphTools
{
    public class Kruskal
    {
        List<WeightedEdge> edges;
        List<Node> nodes;
        Dictionary<int,int> nodeColors; //<nodeId, color>
        public List<WeightedEdge> Result { get; protected set; }
        public bool isStarted { get; protected set; }
        public bool isFinished { get; protected set; }
        public int ColorsCount { get; protected set; }



        public Kruskal(ICollection<WeightedEdge> edges, ICollection<Node> nodes)
        {
            this.edges = new List<WeightedEdge>(edges);
            this.nodes = new List<Node>(nodes);
        }

        public void Start()
        {
            DoWork();
        }

        protected void DoWork()
        {
            isStarted = true;
            List<WeightedEdge> kruskalEdges = new List<WeightedEdge>();
            Console.WriteLine("Kruskal: Initialize node colors...");
            InitNodeColors();
            Console.WriteLine("Kruskal: Sorting...");
            edges.Sort();
            Console.WriteLine("Kruskal: Edge analizing...");
            foreach (Edge e in edges)
            {
                int node1Color = nodeColors[(e.Node1 as Node).Id];
                int node2Color = nodeColors[(e.Node2 as Node).Id];
                if (node1Color != node2Color)
                {
                    kruskalEdges.Add((WeightedEdge)e);
                    ChangeColors(node1Color, node2Color);
                }
            }
            ColorsCount = CountColors();

            isFinished = true;
            Result = kruskalEdges;
        }

        protected void InitNodeColors()
        {
            nodeColors = new Dictionary<int, int>();
            for (int i = 0; i < nodes.Count; i++)
            {
                nodeColors.Add(nodes[i].Id, i);
            }
        }

        protected void ChangeColors(Node from, Node to)
        {
            int fromColor = nodeColors[from.Id];
            int toColor = nodeColors[to.Id];
            ChangeColors(fromColor, toColor);
        }

        protected void ChangeColors(int from, int to)
        {
            foreach (var key in nodeColors.Keys.ToArray())
            {
                if (nodeColors[key] == from) nodeColors[key] = to;
            }
        }

        protected int CountColors()
        {
            HashSet<int> colors = new HashSet<int>();
            foreach (int i in nodeColors.Values)
            {
                colors.Add(i);
            }
            return colors.Count;
        }
    }
}
